const int MAXN=100010;
const int MAXM=200010;

struct graph
{
	int a[MAXN],b[MAXM],c[MAXM],d[MAXM],p,vis[MAXN],siz[MAXN],tot;
	void clear()
	{
		memset(a,0,sizeof a);
		memset(vis,0,sizeof vis);
		p=0;
	}
	void addedge(int x,int y,int z)
	{
		c[++p]=a[x]; a[x]=p; b[p]=y; d[p]=z;
		c[++p]=a[y]; a[y]=p; b[p]=x; d[p]=z;
	}
	void search(int k,int fa,int from,llint dist)
	{
		for(int i=a[k];i;i=c[i]) if (b[i]!=fa&&!vis[b[i]])
			search(b[i],k,from,dist+d[i]);
	}
	int findsize(int x,int fa)
	{
		siz[x]=1;
		for(int i=a[x];i;i=c[i]) if (!vis[b[i]]&&b[i]!=fa)
			siz[x]+=findsize(b[i],x);
		return siz[x];
	}
	int findcenter(int x,int fa)
	{
		int i;
		for(i=a[x];i;i=c[i]) if (!vis[b[i]])
		{
			if (b[i]==fa)
			{
				if (2*(tot-siz[x])>tot) break;
			} else
			{
				if (2*siz[b[i]]>tot) break;
			}
		}
		if (i==0) return x;
		for(i=a[x];i;i=c[i]) if (b[i]!=fa&&!vis[b[i]])
		{
			int o=findcenter(b[i],x);
			if (o) return o;
		}
		return 0;
	}
	int findroot(int x)
	{
		tot=findsize(x,0);
		return findcenter(x,0);
	}
	void dfs(int o)
	{
		int k=findroot(o);
		vis[k]=1;
		for(int i=a[k];i;i=c[i]) if (!vis[b[i]]) search(b[i],k,b[i],d[i]);
		for(int i=a[k];i;i=c[i]) if (!vis[b[i]]) dfs(b[i]);
	}
} A;